package everydayone.maxDistance;
/**
 * @Date 2020/03/29
 * @author 王光浩
 * @Thinking 使用DP，最优子结构：对于每一个海洋模块，它离陆地的最近距离要么来自上左方向、要么来自下右方向。
 */
public class MyMethodTwo {
	public int maxDistance(int[][] grid) {
		int n=grid.length;
		boolean f=false;
		//获取每一个0上、左最小值
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(grid[i][j]==1) {
					f=true;
					continue;
				}
				grid[i][j]=2*n;
				if(i>0)grid[i][j]=Math.min(grid[i-1][j], grid[i][j]);
				if(j>0)grid[i][j]=Math.min(grid[i][j-1], grid[i][j]);
			}
		}
		//获取每一个0上、右的最小值
		int res=1;
		for(int i=n-1;i>=0;i--) {
			for(int j=n-1;j>=0;j--) {
				if(grid[i][j]==1) {
					continue;
				}
				if(i>n-1)grid[i][j]=Math.min(grid[i+1][j], grid[i][j]);
				if(j>n-1)grid[i][j]=Math.min(grid[i][j+1], grid[i][j]);
				res=Math.max(grid[i][j], 1);
			}
		}
		return f?res-1:-1;
	}
}
